/*************************************************************************
	> File Name: 004.线性筛.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  8/23 17:32:12 2021
 ************************************************************************/

#include <stdio.h>

//算法思想：
//1. 标记一个范围内的数字是否是合数，没有被标记的则为素数
//2. 算法的空间复杂度为O(n), 时间复杂度为O(n)
//3. 总体思想：用一个整数M 去标记合数 N，其中M和N有如下性质：
//  1) N 中最小的素因子为 p
//  2) N 可以表示成 p * M (说明：p 为最小的素因子，则M一定是最大的因子，M可能是合数，也可能是素数)
//  3) p 一定小于等于 M 中最小的素因子（说明：如果M中有比p更小的因子，那么p就应该是这个比其更小的素因子，所以p一定小于等于 M 中最小的素因子）
//  4) 利用 M * P'(所有不大于M 中最小素因子的素数的集合) 标记 N1, N2, N3

//若N = 30，则p = 2， M = 15
//若N = 8， 则p = 2， M = 4
//若N = 45，则p = 3， M = 15
//若M = 4，则其最小素因子为2，P'只能等于2，能标记的数为 2 * 4 = 8
//若M = 25，则可以标记的N为 25 * 2， 25 * 3， 25 * 4
//若M = 45，则可以标记的N为 45 * 2， 45 * 3

#define MAX_N 100
int prime[MAX_N + 5];

void solve() {
    for (int i = 2; i <= MAX_N; i++) { //枚举M
        if (!prime[i]) prime[++prime[0]] = i; //记录素数
        for (int j = 1; j <= prime[0]; j++) { //素数表中枚举素数
            if (prime[j] * i > MAX_N)  break;
            prime[prime[j] * i] = 1; //标记M * p' 的值为合数， prime[j] 为 p', i为M
            if (i % prime[j] == 0) break; //prime[j]已经是i的最小素因子了，结束标记，保证了p一定小于等于M的最小素因子，避免重复标记
        }
    }
}


int main() {
    solve();
    for (int i = 1; i <= prime[0]; i++) {
        printf("%d\n", prime[i]);
    }
    return 0;
}
